#include"./head/find_way.h"
Graph graph = {0};
//定义在myhead.h里 邻接表存储图 每行头节点AdjList 元素Node
/*    int vertex;           // 顶点
    int line;            // 边所属的线路
    struct Node* next;    // 下一个节点*/
char visit_place[256];
int  place_count=19;
int count_use = 0;
const char* get_place_name(int node_id) {
    for(int i = 0; i < place_count; i++) {
        if(place_map[i].node_id == node_id) {
            return place_map[i].name;
        }
    }
    return NULL; // 找不到返回 NULL
}
void addEdge(Graph* graph, int src, int dest, int line) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->vertex = dest;
    node->line = line;
    node->next = graph->array[src].head;
    graph->array[src].head = node;

    node = (Node*)malloc(sizeof(Node));
    node->vertex = src;
    node->line = line;
    node->next = graph->array[dest].head;
    graph->array[dest].head = node;
}

// BFS 求最短路径
void BFS_shortest_path(Graph* graph, int start, int end) {
    count_use = 0;  // 每次运行前重置，否则多次调用会累加

    int visited[V] = {0};
    int parent[V];      // 记录前驱
    int parent_line[V]; // 记录到达该点所用的线路
    for (int i = 0; i < V; i++) parent[i] = -1;

    int queue[V], front = 0, rear = 0;
    queue[rear++] = start;
    visited[start] = 1;

    while (front < rear) {
        int u = queue[front++];
        if (u == end) break;

        Node* p = graph->array[u].head;
        while (p) {
            int v = p->vertex;
            if (!visited[v]) {
                visited[v] = 1;
                parent[v] = u;
                parent_line[v] = p->line;
                queue[rear++] = v;
            }
            p = p->next;
        }
    }

    if (!visited[end]) {
        printf("No path from %d to %d\n", start, end);
        return;
    }

    // 回溯路径
    int path[V], lines[V];
    int v = end;
    while (v != start) {
        path[count_use] = v;
        lines[count_use] = parent_line[v];
        v = parent[v];
        count_use++;
    }
    path[count_use] = start;

    // 输出线路
    printf("Shortest path from %d to %d via lines: ", start, end);
    visit_place[0] = '\0';
    int last_line = -1;
    int pos = 0;

    for (int i = count_use; i >= 0; i--) {
        const char* name = get_place_name(path[i]);
        if (!name) name = "?";

        if (lines[i] != last_line && last_line != -1) {
            pos += snprintf(visit_place + pos, sizeof(visit_place) - pos, "(换乘%d号线)->", lines[i]);
        } else if (pos > 0) {
            pos += snprintf(visit_place + pos, sizeof(visit_place) - pos, "->");
        }

        pos += snprintf(visit_place + pos, sizeof(visit_place) - pos, "%s", name);

        last_line = lines[i];
    }
    printf("%s\n", visit_place);
}



void initGraph() {
    

    // 一号线 1~7
    for(int i=1;i<7;i++) addEdge(&graph, i, i+1, 1);

    // 二号线 8~12
    addEdge(&graph, 8, 9, 2);
    addEdge(&graph, 9, 3, 2);   // 9 ↔ 3 属于2号线
    addEdge(&graph, 3, 10, 2);
    addEdge(&graph, 10, 11, 2);
    addEdge(&graph, 11, 12, 2);

    // 三号线 13~16
    addEdge(&graph, 13, 11, 3);
    addEdge(&graph, 11, 14, 3);
    addEdge(&graph, 14, 15, 3);
    addEdge(&graph, 15, 16, 3);

    // 四号线 17~19
    addEdge(&graph, 17, 18, 4);
    addEdge(&graph, 18, 16, 4);
    addEdge(&graph, 16, 19, 4);


}
